Hybridizing Non-dominated Sorting Algorithms: Divide-and-Conquer Meets Best Order Sort

摘要

Many production-grade algorithms benefit from combining an asymptoticallyefficient algorithm for solving big problem instances, by splitting them intosmaller ones, and an asymptotically inefficient algorithm with a very smallimplementation constant for solving small subproblems. A well-known example isstable sorting, where mergesort is often combined with insertion sort toachieve a constant but noticeable speed-up. We apply this idea to non-dominated sorting. Namely, we combine thedivide-and-conquer algorithm, which has the currently best known asymptoticruntime of $O(N (\log N)^{M - 1})$, with the Best Order Sort algorithm, whichhas the runtime of $O(N^2 M)$ but demonstrates the best practical performanceout of quadratic algorithms. Empirical evaluation shows that the hybrid's running time is typically notworse than of both original algorithms, while for large numbers of points itoutperforms them by at least 20%. For smaller numbers of objectives, thespeedup can be as large as four times.